package leet_code;

import java.util.*;

/**
 * 滑动窗口相关
 */
public class A_3_SlidingWindow {
    /**
     * 3. 无重复字符的最长子串
     * https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
     * 中等
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * <p>
     * 示例 1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * <p>
     * 示例 2:
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * <p>
     * 示例 3:
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * <p>
     * <p>
     * 提示：
     * 0 <= s.length <= 5 * 10^4
     * s 由英文字母、数字、符号和空格组成
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        //判断子传是否重复
        int p ;
        int q = 0;
        int maxSubStrLen = 1;
        //存储不重复字串里各字符及其位置
        Map<Character, Integer> charMap = new HashMap<>();
        while (q < chars.length) {
            if (charMap.containsKey(chars[q])) {
                Integer repeatCharIndex = charMap.get(chars[q]);
                if (repeatCharIndex + 1 == q) {
                    p = q;
                    charMap = new HashMap<>();
                    charMap.put(chars[p], p);
                    q++;
                } else {
                    p = repeatCharIndex + 1;
                    charMap = new HashMap<>();
                    for (int i = p; i <= q; i++) {
                        charMap.put(chars[i], i);
                    }
                    q++;
                }
            } else {
                charMap.put(chars[q], q);
                maxSubStrLen = Math.max(maxSubStrLen, charMap.size());
                q++;
            }
        }
        return maxSubStrLen;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * 中等
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     *
     * 示例 1:
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
     *
     *  示例 2:
     * 输入: s = "abab", p = "ab"
     * 输出: [0,1,2]
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
     *
     *
     * 提示:
     * 1 <= s.length, p.length <= 3 * 10^4
     * s 和 p 仅包含小写字母
     * @param s
     * @param p
     */
    public List<Integer> findAnagrams(String s, String p) {
        //记录p串中的char set
        //将p按照char从大到小排序,生成一个有序字符数组
        //遍历s,发现存在其中的字符 todo 待优化
        char[] chars = p.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char aChar : chars) {
            set.add(aChar);
        }
        Arrays.sort(chars);
        char[] sChars = s.toCharArray();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < sChars.length; i++) {
            if (set.contains(sChars[i])) {
                if (i + chars.length - 1 < sChars.length) {
                    char[] charsSub = Arrays.copyOfRange(sChars, i, i + chars.length);
                    Arrays.sort(charsSub);
                    boolean isEq = true;
                    for (int j = 0; j < chars.length; j++) {
                        if (charsSub[j] != chars[j]) {
                            isEq = false;
                            break;
                        }
                    }
                    if (isEq) {
                        res.add(i);
                    }
                } else {
                    //后面的字符不满足长度
                    break;
                }
            } else {
                continue;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        A_3_SlidingWindow slidingWindow = new A_3_SlidingWindow();

        //无重复字符的最长子串
//        String str = "abcabcbb";
//        String str = "bbbbb";
//        String str = "pwwkew";
//        System.out.println(slidingWindow.lengthOfLongestSubstring(str));
//        -----------------------------------

//        找到字符串中所有字母异位词
//        String s = "cbaebabacd", p = "abc";
        String s = "abab", p = "ab";
        List<Integer> anagrams = slidingWindow.findAnagrams(s, p);
        for (Integer anagram : anagrams) {
            System.out.println(anagram);
        }
    }
}
